package tree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class TypeAheadSearch
{
  // REGULAR EXPRESSIONS:
  private static final String INTEGER_RE = "[0-9]+"; // Matches any non
  // negative integer
  private static final String INTEGER_GROUP_RE = "(" + INTEGER_RE + ")"; // Group
  // version
  private static final String FLOAT_RE = "[0-9]+(?:.[0-9]*)?"; // INVARIANT:
                                                               // always
  // positive
  private static final String FLOAT_GROUP_RE = "(" + FLOAT_RE + ")"; // Group
  // version
  private static final String ID_RE = "\\w+"; // NOTE: we assume that
  // an ID must start
  // with a letter,
  // and can be
  // composed of
  // letters, numbers
  // and underscores
  // only
  private static final String ID_GROUP_RE = "(" + ID_RE + ")"; // Group
  // version
  private static final String SEPARATOR_RE = "(?: |\\t)"; // We consider just
                                                          // spaces
  // as separators
  private static final String STRING_GROUP_RE = "(\\S*.*)"; // Strings starts
  // with a char
  // and can have
  // spaces
  private static final String COMMAND_RE = "(ADD)|(DEL)|(W?QUERY)"; // Matches
  // all
  // the 4
  // possible
  // command
  // instructions
  private static final String COMMAND_GROUP_RE = "(" + COMMAND_RE + ")"
      + SEPARATOR_RE + STRING_GROUP_RE; // Matches any command line,
  // grouping the command
  private static final String TYPE_RE = "user|topic|question|board"; // Matches
  // one
  // of
  // the 4
  // types
  private static final String TYPE_GROUP_RE = "(" + TYPE_RE + ")"; // Group
  // version
  private static final String BOOST_GROUP_RE = "((?:" + TYPE_RE + "|(?:"
      + ID_RE + ")):" + FLOAT_RE + SEPARATOR_RE + ")"; // Matches a boost
  private static final String TYPE_BOOST_RE = TYPE_GROUP_RE + ":"
      + FLOAT_GROUP_RE; // Matches a "type" boost
  private static final String ID_BOOST_RE = ID_GROUP_RE + ":" + FLOAT_GROUP_RE; // Matches
                                                                                // an
                                                                                // "id"
                                                                                // boost

  // REGULAR EXPRESSIONS for the four possible command lines:
  // Add statements format: ADD <type> <id> <score> <data string that can
  // contain spaces>
  private static final String ADD_STMT_RE = "ADD" + SEPARATOR_RE
      + TYPE_GROUP_RE + SEPARATOR_RE + ID_GROUP_RE + SEPARATOR_RE
      + FLOAT_GROUP_RE + SEPARATOR_RE + STRING_GROUP_RE;
  // Del statements format: DEL <id>
  private static final String DEL_STMT_RE = "DEL" + SEPARATOR_RE + ID_GROUP_RE;
  // Query statements format: QUERY <number of results > <query string that
  // can contain spaces>
  private static final String QUERY_STMT_RE = "QUERY" + SEPARATOR_RE
      + INTEGER_GROUP_RE + SEPARATOR_RE + STRING_GROUP_RE;
  // WQuery statements format: WQUERY <number of results> <number of boosts>
  // (<type>:<boost>)* (<id>:<boost>)* <query string that can contain spaces>
  private static final String WQUERY_STMT_RE = "WQUERY" + SEPARATOR_RE
      + INTEGER_GROUP_RE + SEPARATOR_RE + INTEGER_GROUP_RE + SEPARATOR_RE
      + BOOST_GROUP_RE + "*+" + STRING_GROUP_RE;

  // PATTERNS (compiled only once to improve performance):
  private static final Pattern pAddCommand = Pattern.compile(ADD_STMT_RE);
  private static final Pattern pDelCommand = Pattern.compile(DEL_STMT_RE);
  private static final Pattern pQueryCommand = Pattern.compile(QUERY_STMT_RE);
  private static final Pattern pWQueryCommand = Pattern.compile(WQUERY_STMT_RE);
  private static final Pattern pTypeBoost = Pattern.compile(TYPE_BOOST_RE);
  private static final Pattern pIdBoost = Pattern.compile(ID_BOOST_RE);
  // Matches just the command string (any of the 4 legal commands)
  private static final Pattern pCommand = Pattern.compile(COMMAND_GROUP_RE);

  // DB and Output are stored as vectors
  // private static final PrefixTree prefixTree = new PrefixTree();
  private static final PatriciaTree prefixTree = new PatriciaTree();
  private static final Trie keyTrie = new Trie();
  // private static HashMap<String, Item> recordsMap;

  private static final ArrayList<Boost> typeBoosts = new ArrayList<Boost>(26);
  private static final ArrayList<Boost> idBoosts = new ArrayList<Boost>(26);

  // The collected while commands are inserted from stdin but printed
  // only once all commands have been completed

  /**
   * Main method: handles IO and, for each line inserted from System.in, calls
   * the
   * right function to process the command.
   * When all the input has been read and processed, outputs the results of the
   * queries on System.out
   * 
   * @param args: Possible arguments for the class (none processed at the
   *        moment).
   */
  public static void main(String[] args)
      throws IOException
  {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String inputLine;
    String command;
    int N; // Number of commands to expect from the input
    int counter = 0;

    if ((inputLine = in.readLine()) == null || inputLine.length() == 0) {
      throw new Error(
          "Bad formatted input: need to insert the number of commands first");
    }
    else {
      // INVARIANT: input is inserted correctly formatted according to
      // challenge specs
      N = Integer.parseInt(inputLine);
    }

    // recordsMap = new HashMap<String, Item>(N/2, 0.5f);

    while (counter++ < N) {
      // Tries to read N lines
      inputLine = in.readLine();
      // INVARIANT: input is inserted correctly formatted according to
      // challenge specs
      Matcher commandMatcher = pCommand.matcher(inputLine);
      commandMatcher.matches();
      command = commandMatcher.group(1);

      if (command.equals("ADD")) {
        processAddCommand(inputLine);
      }
      else if (command.equals("DEL")) {
        processDelCommand(inputLine);
      }
      else if (command.equals("QUERY")) {
        // output.add(
        processQueryCommand(inputLine);
      }
      else if (command.equals("WQUERY")) {
        // output.add(
        processWQueryCommand(inputLine);
      }
      // WARNING: An empty line or Ctrl-Z terminates the program without
      // producing any output!!!
    }

    // Prints the generated output on standard output
    // for (String s:output) {
    // System.out.println(s);
    // }

    // DEBUG://printDB();
  }

  /**
   * Takes an ADD command line and, if everything is properly formatted,
   * performs the insertion of a new element in the DB.
   * 
   * @param addCommand: The command line, as received from the input.
   */
  private static void processAddCommand(String addCommand)
  {

    Matcher commandMatcher = pAddCommand.matcher(addCommand);
    commandMatcher.matches();
    // String type = ;
    // String id = ;
    // float score = ;
    // String data = ;
    // Keeps record sorted
    String id = commandMatcher.group(2);
    Item newItem = new Item(commandMatcher.group(1), id,
        Float.parseFloat(commandMatcher.group(3)), commandMatcher.group(4));
    // recordsMap.put(id, newItem);
    keyTrie.insertString(id, newItem);

    for (String s : newItem.data) {
      prefixTree.insertString(s, newItem);
    }
    // printDB();
    // System.out.println("-----------------------------");
  }

  /**
   * Takes a DEL command line and, if everything is properly formatted,
   * performs the deletion of the element with the given ID from the DB.
   * 
   * @param delCommand: The command line, as received from the input.
   */
  private static void processDelCommand(String delCommand)
  {

    Matcher commandMatcher = pDelCommand.matcher(delCommand);
    commandMatcher.matches();
    String id = commandMatcher.group(1);

    // Item item = recordsMap.get(id);
    Item item = keyTrie.search(id);
    for (String s : item.data) {
      prefixTree.removeString(s, item);
    }
    // keyTrie.removeKey(id);
    // INVARIANT: all requests are legitimate, so execution should never
    // reach this point.
    // At the moment ignores possible unlegitimate ones (should throw
    // exception on id not found?)
  }

  /**
   * Takes a QUERY command line and, if everything is properly formatted,
   * performs the required query on the DB. To improve performance, while
   * examining the DB for data matching the query, only the best n results are
   * kept in a sorted vector, where n is the maximum number of results
   * accepted by the query (specified in the command line).
   * 
   * @param queryCommand: The command line, as received from the input;
   * @return: A string containing the list of the IDs matching the query,
   *          separated by spaces, and sorted according to: 1) Score 2)
   *          Creation time (when there is a tie on the score, most recents
   *          elements go first)
   */
  private static void processQueryCommand(String queryCommand)
  {

    Matcher commandMatcher = pQueryCommand.matcher(queryCommand);
    commandMatcher.matches();
    int numberOfResults = Integer.parseInt(commandMatcher.group(1));
    if (numberOfResults == 0) {
      System.out.println("");
      return;
    }

    String queryString = commandMatcher.group(2);
    String[] tokens = queryString.toLowerCase().split(SEPARATOR_RE); // INVARIANT:
    // Search
    // is
    // case
    // insensitive
    // SortedVector<Item> resultsVector = new SortedVector<Item>();
    Item[] resultsHeap = new Item[numberOfResults];

    int heapSize = 0, i;
    int pos, childPos, rightPos, parentPos;

    // resultsVector.setMaxSize(numberOfResults);
    try {
      for (Item item : prefixTree.search(tokens)) {

        if (heapSize == numberOfResults) {

          if (item.score < resultsHeap[0].score) {
            // This item is too big for the queue
            continue;
          }

          // Creates a new item with the proper score, given by the
          // original item's score multiplied by the boost that can be
          // applied.

          pos = 0;
          // Bubble up the greater child until hitting a leaf.
          childPos = 2 * pos + 1; // leftmost child position
          while (childPos < heapSize) {
            // Set childpos to index of greater child.
            rightPos = childPos + 1;
            if (rightPos < heapSize
                && resultsHeap[childPos].compareTo(resultsHeap[rightPos]) < 0) {
              childPos = rightPos;
            }
            // Move the greater child up.
            if (resultsHeap[childPos].compareTo(item) < 0) {
              break;
            }

            resultsHeap[pos] = resultsHeap[childPos];

            pos = childPos;
            childPos = 2 * pos + 1;
          }
          resultsHeap[pos] = item;
        }
        else {
          // Creates a new item with the proper score, given by the
          // original item's score multiplied by the boost that can be
          // applied.

          resultsHeap[heapSize] = item;
          pos = heapSize++;
          // Follow the path to the root, moving parents down until it finds a
          // place
          // where new_item fits.
          while (pos > 0) {
            parentPos = (pos - 1) >> 1;
            if (item.compareTo(resultsHeap[parentPos]) > 0) {
              resultsHeap[pos] = resultsHeap[parentPos];
              pos = parentPos;
            }
            else {
              break;
            }
          }
          resultsHeap[pos] = item;

        }
      }
    }
    catch (NullPointerException e) {
      System.out.println("");
      return;
    }

    if (heapSize == 0) {
      System.out.println("");
      return;
    }

    Arrays.sort(resultsHeap, 0, heapSize);

    // Creates the output string
    StringBuilder out = new StringBuilder();
    for (i = 0 ; i < heapSize - 1 ; i++) {
      Item item = resultsHeap[i];
      out.append(item.id);
      out.append(" ");
    }
    Item item = resultsHeap[i];
    out.append(item.id);
    System.out.println(out.toString());
  }

  /**
   * Takes a WQUERY command line and, if everything is properly formatted,
   * performs the required query on the DB. Weighted queries requires a few
   * extra steps than regular queries:
   * 1) Boost criteria must be identified from the command line;
   * 2) For every record in the DB matching the query string, the
   * weighted score must be computed.
   * 
   * To improve performance, while examining the DB for data matching the
   * query, only the best n results are kept in a sorted vector, where n is
   * the maximum number of results accepted by the query (specified in the
   * command line). Since a different score must be computed for each wquery
   * and DB elements' score shouldn't be modified, for each matching record a
   * new Item object is created, inheriting all attributes from the original
   * one but the score, which is instead computed as the weighted version
   * according to the query's boosts factors. An alternative could have been
   * creating coupling each Item with its weight factor or weighted score, and
   * defining a different external comparison methods for Entities, but,
   * besides violating encapsulation and complicating the design, the benefits
   * of this approach wouldn't be clearly significant.
   * 
   * @param wqueryCommand: The command line, as received from the input;
   * @return: A string containing the list of the IDs matching the query,
   *          separated by spaces, and sorted according to:
   *          1) Score
   *          2) Creation time (when there is a tie on the score,
   *          most recent elements go first)
   */
  private static void processWQueryCommand(String wqueryCommand)
  {

    Matcher commandMatcher = pWQueryCommand.matcher(wqueryCommand);
    commandMatcher.matches();
    Matcher boostMatcher;

    int numberOfResults = Integer.parseInt(commandMatcher.group(1));
    if (numberOfResults == 0) {
      System.out.println("");
      return;
    }

    int i_numberOfBoosts = Integer.parseInt(commandMatcher.group(2));

    // (boost)* captures as a group only the last occurence of boost, so we
    // need to take the substring from the end of the previous group
    // to the end of the last occurrence of a boost
    if (i_numberOfBoosts > 0) {
      idBoosts.clear();
      typeBoosts.clear();
      // INVARIANT: Input is well formed, so the third group exists and
      // matches the last boost in the input line.
      String[] as_boosts = wqueryCommand.substring(commandMatcher.end(2) + 1,
          commandMatcher.end(3)).split(SEPARATOR_RE);

      // Additional check (redundant assuming the input is well formatted)
      /*
       * if (as_boosts.length != i_numberOfBoosts) {
       * throw new Error(
       * "Bad formatted input: please check the challenge specifications for WQUERY commands"
       * );
       * }
       */

      int counter = 0;
      // Creates the lists of boosts
      // INVARIANT: According to specifications, first comes type-boosts,
      // and then id-boosts, but they are not mixed with each other.
      while (counter < i_numberOfBoosts
          && (boostMatcher = pTypeBoost.matcher(as_boosts[counter])).matches()) {
        counter++;
        typeBoosts.add(new Boost(boostMatcher.group(1), Float
            .parseFloat(boostMatcher.group(2))));
      }

      while (counter < i_numberOfBoosts) {
        boostMatcher = pIdBoost.matcher(as_boosts[counter]);
        boostMatcher.matches();
        // INVARIANT: types descriptor are reserved words and so they can't
        // appear as IDs
        /*
         * if (pTypeBoost.matcher(as_boosts[counter]).matches()){
         * throw new Error(
         * "Bad formatted input: types are reserved words and can't " +
         * "be used as ID; Please check the challenge specifications " +
         * "for WQUERY commands");
         * }
         */
        counter++;
        idBoosts.add(new Boost(boostMatcher.group(1), Float
            .parseFloat(boostMatcher.group(2))));
      }

      // Additional check (redundant assuming the input is well formatted)
      /*
       * if (counter != i_numberOfBoosts) {
       * throw new Error(
       * "Bad formatted input: please check the challenge specifications for WQUERY commands"
       * );
       * }
       */
    }

    String queryString = commandMatcher.group(4);
    String[] tokens = queryString.toLowerCase().split(SEPARATOR_RE);
    // INVARIANT: Search is case insensitive

    ItemResult[] resultsHeap = new ItemResult[numberOfResults];

    int heapSize = 0, i;
    int pos, childPos, rightPos, parentPos;

    try {
      for (Item item : prefixTree.search(tokens)) {

        if (heapSize == numberOfResults) {

          // Computes the boost factor first
          float mul = 1.0f;
          for (Boost boost : typeBoosts) {
            if (item.type.equals(boost.pattern)) {
              mul *= boost.mul;
              // INVARIANT: assuming each type boost can match only once
              break;
            }
          }
          for (Boost boost : idBoosts) {
            if (item.id.equals(boost.pattern)) {
              mul *= boost.mul;
              // INVARIANT: assuming each ID boost can match only once
              break;
            }
          }

          if (item.score * mul < resultsHeap[0].score) {
            // This item is too big for the queue
            continue;
          }

          // Creates a new item with the proper score, given by the
          // original item's score multiplied by the boost that can be
          // applied.

          ItemResult itemR = new ItemResult(item.id, item.score * mul,
              item.creationTime);

          pos = 0;
          // Bubble up the greater child until hitting a leaf.
          childPos = 2 * pos + 1; // leftmost child position
          while (childPos < heapSize) {
            // Set childpos to index of greater child.
            rightPos = childPos + 1;
            if (rightPos < heapSize
                && resultsHeap[childPos].compareTo(resultsHeap[rightPos]) < 0) {
              childPos = rightPos;
            }
            // Move the greater child up.
            if (resultsHeap[childPos].compareTo(itemR) < 0) {
              break;
            }

            resultsHeap[pos] = resultsHeap[childPos];

            pos = childPos;
            childPos = 2 * pos + 1;
          }
          resultsHeap[pos] = itemR;
        }
        else {
          // The Heap isn't full yet

          // Computes the boost factor first
          float mul = 1.0f;
          for (Boost boost : typeBoosts) {
            if (item.type.equals(boost.pattern)) {
              mul *= boost.mul;
              // INVARIANT: assuming each type boost can match only once
              break;
            }
          }
          for (Boost boost : idBoosts) {
            if (item.id.equals(boost.pattern)) {
              mul *= boost.mul;
              // INVARIANT: assuming each ID boost can match only once
              break;
            }
          }

          // Creates a new item with the proper score, given by the
          // original item's score multiplied by the boost that can be
          // applied.

          ItemResult itemR = new ItemResult(item.id, item.score * mul,
              item.creationTime);
          resultsHeap[heapSize] = itemR;
          pos = heapSize++;
          // Follow the path to the root, moving parents down until it finds a
          // place
          // where new_item fits.
          while (pos > 0) {
            parentPos = (pos - 1) >> 1;
            if (itemR.compareTo(resultsHeap[parentPos]) > 0) {
              resultsHeap[pos] = resultsHeap[parentPos];
              pos = parentPos;
            }
            else {
              break;
            }
          }
          resultsHeap[pos] = itemR;

        }
      }
    }
    catch (NullPointerException e) {
      System.out.println("");
      return;
    }

    if (heapSize == 0) {
      System.out.println("");
      return;
    }

    Arrays.sort(resultsHeap, 0, heapSize);

    // Creates the output string
    StringBuilder out = new StringBuilder();
    for (i = 0 ; i < heapSize - 1 ; i++) {
      ItemResult item = resultsHeap[i];
      out.append(item.id);
      out.append(" ");
    }
    ItemResult item = resultsHeap[i];
    out.append(item.id);
    System.out.println(out.toString());
  }

  private static class PatriciaTree
  {

    private static class PatriciaTreeNode
    {
      private String label;

      public PatriciaTreeNode()
      {

      }

      public PatriciaTreeNode(String l, Item item)
      {
        this.label = l;
        this.items.add(item);
      }

      @SuppressWarnings("unchecked")
      public PatriciaTreeNode(String label,
          ArrayList<PatriciaTreeNode> childrenReference, HashSet<Item> items)
      {
        this.label = label;
        this.children = childrenReference;
        this.items = (HashSet<Item>) (items.clone());
      }

      private ArrayList<PatriciaTreeNode> children = new ArrayList<PatriciaTreeNode>();
      private HashSet<Item> items = new HashSet<Item>();

      public PatriciaTreeNode search(String s)
      {
        int l = 0, r = children.size() - 1, pos = 0;
        char tmp_c, c;
        try {
          c = s.charAt(0);
        }
        catch (StringIndexOutOfBoundsException e) {
          return null;
        }
        while (l <= r) {
          pos = (l + r) / 2;
          PatriciaTreeNode child = children.get(pos);
          String label = child.label;
          int l_len = label.length();
          tmp_c = label.charAt(0);
          if (tmp_c == c) {
            int i = 1;
            int s_len = s.length();

            int n = Math.min(s_len, l_len);
            for ( ; i < n ; i++) {
              if (s.charAt(i) != label.charAt(i)) {
                break;
              }
            }
            if (i == s_len) {
              return child;
            }
            else if (i == l_len) {
              return child.search(s.substring(i));
            }
            else {
              return null;
            }
          }
          else if (tmp_c < c) {
            l = pos + 1;
          }
          else {
            r = pos - 1;
          }
        }

        return null;
      }

      public void insertChild(String s, Item item)
      {
        int size = children.size(), l = 0, r = size - 1, pos = 0;
        int s_len = s.length();
        char tmp_c, c;
        try {
          c = s.charAt(0);
        }
        catch (StringIndexOutOfBoundsException e) {
          return;
        }
        while (l <= r) {
          pos = (l + r) / 2;
          PatriciaTreeNode child = children.get(pos);
          String label = child.label;
          int l_len = label.length();

          tmp_c = label.charAt(0);
          if (tmp_c == c) {

            int n = Math.min(l_len, s_len);
            int i = 1;
            for ( ; i < n ; i++) {
              if (label.charAt(i) != s.charAt(i)) {
                break;
              }
            }
            if (i < l_len) {
              String restOfl = label.substring(i);
              child.label = s.substring(0, i);

              PatriciaTreeNode new_child = new PatriciaTreeNode(restOfl,
                  child.children, child.items);
              child.children = new ArrayList<PatriciaTreeNode>(2); // old var
                                                                   // has
                                                                   // exausted
                                                                   // its life
              child.children.add(new_child);
              child.items.add(item);
              if (i < s_len) {
                String restOfs = s.substring(i);
                new_child = new PatriciaTreeNode(restOfs, item);
                if (restOfl.compareTo(restOfs) < 0) {
                  child.children.add(new_child);
                }
                else {
                  child.children.add(0, new_child);
                }
              }
            }
            else if (i < s_len) {
              child.items.add(item);
              String restOfs = s.substring(i);
              child.insertChild(restOfs, item);
            }
            else {
              child.items.add(item);
            }
            return;
          }
          else if (tmp_c < c) {
            l = pos + 1;
          }
          else {
            r = pos - 1;
          }
        }

        PatriciaTreeNode node = new PatriciaTreeNode(s, item);
        this.children.add(l, node);
        return;
      }

      public void removeItem(String s, Item item)
      {
        int l = 0, r = children.size() - 1, pos = 0;
        char tmp_c, c;
        try {
          c = s.charAt(0);
        }
        catch (StringIndexOutOfBoundsException e) {
          return;
        }
        while (l <= r) {
          pos = (l + r) / 2;
          PatriciaTreeNode child = children.get(pos);
          String label = child.label;
          int l_len = label.length();
          tmp_c = label.charAt(0);
          if (tmp_c == c) {
            child.items.remove(item);
            int i = 1;
            int s_len = s.length();

            int n = Math.min(s_len, l_len);
            for ( ; i < n ; i++) {
              if (s.charAt(i) != label.charAt(i)) {
                break;
              }
            }
            if (i == l_len && i < s_len) {
              child.removeItem(s.substring(i), item);
              return;
            }
            else {
              return;
            }
          }
          else if (tmp_c < c) {
            l = pos + 1;
          }
          else {
            r = pos - 1;
          }
        }

      }
    }

    private PatriciaTreeNode root = new PatriciaTreeNode();

    public void insertString(String label, Item item)
    {
      root.insertChild(label, item);
    }

    public void removeString(String s, Item item)
    {
      root.removeItem(s, item);
    }

    public HashSet<Item> search(String s)
    {
      try {
        return root.search(s).items;
      }
      catch (NullPointerException e) {
        return null;
      }
    }

    public HashSet<Item> search(String[] sArray)
    {
      HashSet<Item> results, tmp_result, tmp;
      try {
        results = search(sArray[0]);
      }
      catch (IndexOutOfBoundsException e) {
        return null;
      }

      int n = sArray.length;
      for (int i = 1 ; i < n ; i++) {
        try {
          if (results.isEmpty()) {
            return results;
          }
          tmp_result = search(sArray[i]);
          tmp = new HashSet<Item>(results.size());
          for (Item item : tmp_result) {
            if (results.contains(item)) {
              tmp.add(item);
            }
          }
          results = tmp;
        }
        catch (NullPointerException e) {
          return null;
        }
      }
      return results;
    }

  }

  private static class Trie
  {

    private static class TrieNode
    {
      private char c;
      private final ArrayList<TrieNode> children = new ArrayList<TrieNode>();
      private Item item = null;

      public TrieNode()
      {

      }

      public TrieNode(char c)
      {
        this.c = c;
      }

      public TrieNode search(char c)
      {
        int l = 0, r = children.size() - 1, pos = 0;
        char tmp_c;
        while (l <= r) {
          pos = (l + r) / 2;
          tmp_c = children.get(pos).c;
          if (tmp_c == c) {
            return children.get(pos);
          }
          else if (tmp_c < c) {
            l = pos + 1;
          }
          else {
            r = pos - 1;
          }
        }

        return null;
      }

      public TrieNode insertChild(char c)
      {
        int size = children.size(), l = 0, r = size - 1, pos = 0;
        char tmp_c;
        while (l <= r) {
          pos = (l + r) / 2;
          TrieNode child = children.get(pos);
          tmp_c = child.c;
          if (tmp_c == c) {
            return child;
          }
          else if (tmp_c < c) {
            l = pos + 1;
          }
          else {
            r = pos - 1;
          }
        }

        TrieNode node = new TrieNode(c);
        this.children.add(l, node);
        return node;
      }

      public void setItem(Item item)
      {
        this.item = item;
      }
      /*
       * public void removeItem(Item item){
       * item = null;
       * }
       */
    }

    private TrieNode root = new TrieNode();

    public void insertString(String s, Item item)
    {
      char[] cArray = s.toCharArray();
      TrieNode node = root;
      for (char c : cArray) {
        node = node.insertChild(c);
      }
      node.setItem(item);
    }

    /*
     * public void removeKey(String s, Item item){
     * char[] cArray = s.toCharArray();
     * TrieNode node = root;
     * for (char c: cArray){
     * node = node.search(c);
     * }
     * node.removeItem(item);
     * }
     */

    public Item search(String s)
    {
      char[] cArray = s.toCharArray();
      TrieNode node = root, child;
      for (char c : cArray) {
        try {
          child = node.search(c);
          node = child;
        }
        catch (NullPointerException e) {
          return null;
        }
      }
      return node.item;
    }

  }

  /**
   * class Item
   * 
   * @author mlarocca
   *         Models an item (either a topic, an user, a board or a
   *         question) stored in the local DB.
   * 
   */
  private static class Item
      implements Comparable<Item>
  {
    protected String type;
    protected String id;
    protected float score;
    protected final String[] data;
    private int creationTime;

    private static int time = 0;

    /**
     * Constructor: copy the attributes of the item from the input
     * parameters and inits the creation time according to a private
     * 'clock'. The attributes are designed as 'final', and so there is no
     * setter available to change their values.
     * 
     * @param type
     *        : The item's type;
     * @param id
     *        : The item's ID;
     * @param score
     *        : The score associated to the item;
     * @param data
     *        : The data associated to the item.
     */
    public Item(String type, String id, float score, String data)
    {
      // INVARIANT: ID are unique
      this.type = type;
      this.id = id;
      this.score = score;

      this.data = data.toLowerCase().split(SEPARATOR_RE);
      // Arrays.sort(this.data);
      this.creationTime = ++time; // Keeps track of the creation time
      // to make it easy to check which of
      // two Entities is newer
    }

    /**
     * Implemented to achieve compatibility with Comparable Interface. Items
     * are ordered according to the following criteria: 1) Score: higher
     * score means lower (better) rank; 2) Novelty: when two items have the
     * same score, the newest has lower (better) rank.
     * 
     * @param o_i_other: the item to be compared to;
     * @return: An int indicating which of the two items has lower rank: -
     *          If the returned value is <0, it is this item; - If the
     *          returned value is >0, it is the other item; - The case in
     *          which the two items have the same rank is not possible.
     */
    @Override
    public int compareTo(Item other)
    {
      if (this.score > other.score) {
        return -1; // Highest score "wins"
      }
      else if (this.score < other.score) {
        return 1;
      }
      else {
        return other.creationTime - this.creationTime;
      }
    }

    /**
     * Utility function: prints the item in an informative format to a
     * specific PrintStream.
     * 
     * @param out: The output stream on which the data has to be printed.
     *        private void print(PrintStream out) {
     *        out.println("ID: " + this.id + " of type " + this.type);
     *        out.println("\t creation time: " + this.creationTime
     *        + "; score: " + this.score);
     *        out.println("\t " + this.data);
     *        }
     */

  }

  /**
   * class Item
   * 
   * @author mlarocca
   *         Models an item (either a topic, an user, a board or a
   *         question) stored in the local DB.
   * 
   */
  private static class ItemResult
      implements Comparable<ItemResult>
  {
    protected String id;
    protected float score;
    private int creationTime;

    /**
     * Constructor: copy the attributes of the item from the input
     * parameters and inits the creation time according to a private
     * 'clock'. The attributes are designed as 'final', and so there is no
     * setter available to change their values.
     * 
     * @param type
     *        : The item's type;
     * @param id
     *        : The item's ID;
     * @param score
     *        : The score associated to the item;
     * @param data
     *        : The data associated to the item.
     */
    public ItemResult(String id, float score, int creationTime)
    {
      // INVARIANT: ID are unique

      this.id = id;
      this.score = score;
      this.creationTime = creationTime;
    }

    /**
     * Implemented to achieve compatibility with Comparable Interface. Items
     * are ordered according to the following criteria: 1) Score: higher
     * score means lower (better) rank; 2) Novelty: when two items have the
     * same score, the newest has lower (better) rank.
     * 
     * @param o_i_other: the item to be compared to;
     * @return: An int indicating which of the two items has lower rank: -
     *          If the returned value is <0, it is this item; - If the
     *          returned value is >0, it is the other item; - The case in
     *          which the two items have the same rank is not possible.
     */
    @Override
    public int compareTo(ItemResult other)
    {
      if (this.score > other.score) {
        return -1; // Highest score "wins"
      }
      else if (this.score < other.score) {
        return 1;
      }
      else {
        return other.creationTime - this.creationTime;
      }
    }

  }

  /**
   * class Boost
   * 
   * @author mlarocca Models a pair composed by a String and a float, in order
   *         to represent a generic boost (either a type boost or an ID
   *         boost).
   */
  private static class Boost
  {
    private String pattern;
    private float mul;

    /**
     * Constructor: inits the Boost's attributes
     * 
     * @param pattern: The string pattern that specify when the
     *        boost should be applied;
     * @param multiplier: The score boost factor.
     */
    public Boost(String pattern, float multiplier)
    {
      this.pattern = pattern;
      this.mul = multiplier;
    }
  }
}
